A system using multiple tone signalling generally uses the Fourier Transform and its inverse to convert the information between time and frequency domains. Two examples of this type of modulation scheme are: (a) DMT (Discrete Multi-Tone) as used in systems such as ADSL (Asymmetric Digital Subscriber Loop); and (b) COFDM (Carrierless Orthogonal Frequency Division Multiplex), a standard widely adopted for digital terrestrial TV broadcasting.
In these systems, the data to be transmitted are sub-divided (multiplexed) across a number of distinct frequencies (sometimes also referred to as tones or sub-carriers) which are all integer multiples of a fixed basic frequency. The individual tones making up the group are spaced apart by this basic frequency. (In the case of COFDM the group of tones is then shifted up to a much higher frequency range for transmission from an aerial, but that detail is not relevant to the discussion here.) The number of tones used in different systems and within an individual system can vary, anywhere from 10 or so; e.g. for a low bandwidth ADSL upstream link, up to several thousand, e.g. an “8K-carrier” COFDM digital TV transmission.
The key algorithm common to the communication systems under consideration is the Fourier Transform, a mathematical scheme in which a time-varying signal is represented not as a set of values in time but as the sum of a set of sinusoidal waveforms. Each sinusoid in the set has a distinct frequency which is an integer multiple of a base frequency called the analysis frequency. Fourier Transform theory shows that any varying signal can be alternately represented in this way, by defining the unique set of amplitude and phase values for the individual sinusoids which sum together to form the signal wave-shape.
In the general (continuous) case, the size of the set of sinusoids is infinite and the spacing of the individual frequencies is infinitesimal. However the particular type of Fourier Transform used in practical communications systems is the Discrete Fourier Transform (DFT). The term ‘discrete’ is used because the data is processed as a set of distinct samples, not a continuous signal. When a finite sequence of samples is transformed in this way, the size of the set of sinusoids that represent the signal in the frequency domain is also finite. Hereafter, when the Fourier Transform is mentioned, the term ‘discrete’ should be assumed.
In summary, the normal (“forward”) Fourier Transform is used to convert from a series of samples taken in the time domain into an equivalent representation of the same information, namely as a series of values in the frequency domain, describing the amplitude and phase of each of a set of harmonically related sinusoidal waveforms. The reverse process, the Inverse Fourier Transform, performs the opposite operation, summing the waveforms described by the individual amplitude and phase values to re-create a composite waveform as a series of samples in the time domain.
The Fourier Transform and its inverse are relatively complex functions, but they may be implemented without difficulty using well-known algorithms on a digital signal processor. In particular, highly efficient versions of the transforms are known, commonly called the Fast Fourier Transform (FFT) and the Inverse FFT or IFFT, which operate on sample sequences whose lengths are powers of 2, e.g. 256 points or 512 points.
The FFT and IFFT together provide for efficient encoding and decoding of signals. In a transmitter, a set of data bits may be encoded by the IFFT, choosing particular combinations of amplitude and phase for each of the constituent frequency components to represent different data values. After all the data is encoded into the amplitude and phase of each constituent tone, the IFFT is performed to create a time-domain signal which is then transmitted.
For example, it is possible to encode 2 bits of data, representing 4 different possible values (00, 01, 10, 11), on to one tone by simple quadrature modulation, where the amplitude is held constant and four distinct phase values (e.g. +45, +135, +225, +315 degrees, i.e. 90 degrees apart) represent the 4 different combinations. More complex mappings are possible (allowing more bits to be encoded on one tone) using more phase values, or combinations of different amplitudes as well as phases. In practical systems, modulation of one tone can be varied so as to represent as many as 15 or 16 bits in the best case (using 32768 or 65536 distinct combinations of amplitude and phase). Therefore in systems using hundreds of tones, some thousands of bits can be carried in each symbol in good circumstances.
The (forward) FFT is used at the receiver to reverse the process. Once time synchronization with the transmitted waveform has been achieved and equalisation for frequency-dependent phase and amplitude changes (inevitable in the transfer of the signal from transmitter to receiver) has been performed, the FFT is applied to the set of samples making up each received symbol, to reconstruct values of amplitude and phase for each of the tones in use. In general the values obtained by this process are not exactly the same as were initially encoded, for various reasons, including particularly the presence of noise introduced along the transmission path of the signal. Noise is unavoidable in any practical system. However, by applying various techniques to compensate for errors caused by noise, the original data may be recovered with an acceptable level of reliability, provided the system has been configured appropriately, taking into account the signal-transfer characteristics of the transmission path.
In order to ease the work of the receiver in equalizing the received signal for the effects of the transmission route, it is common to insert a short delay between consecutive symbols transmitted. In ADSL, this delay period is called the “cyclic prefix time”, in which what is transmitted is a portion of the signal extracted from the end of the immediately following symbol. The name “cyclic prefix” time derives from the fact that the short sequence has been used as a prefix to the new symbol and is cyclically congruent with it. Note that after equalization, the signal received during the cyclic prefix time is ignored by the receiver. In COFDM, the delay period is called the “guard time”; no signal is transmitted during this time.
The IFFT-FFT (encoding-decoding) process provides for great flexibility in the communications system. Different frequencies in the spectrum covered by the set of tones may have different characteristics in respect of noisiness and attenuation over the communication link (e.g. the phone line in the case of an ADSL system). By varying the encoding details tone by tone, this may be accounted for, so as to maximize the number of bits carried by the symbol in total, even when a particular single tone can only carry a small number of bits. U.S. Pat. No. 4,679,227, which describes multi-tone encoding schemes, presents techniques for accomplishing this.
One property of this type of signal encoding is particularly relevant. The waveform resulting from the IFFT can in principle have very large peak values in it—relative to the average amplitude of the signal as a whole—at points where the particular phases of the individual tones happen to sum together in the same direction. For example, if all tones were using encoded simple 2-bit quadrature modulation, and all the data bits being modulated were zero (or more generally if the same pair of bit values were modulating each tone), then at the start of the time domain symbol created by the IFFT there would be a high amplitude “spike”, since each component waveform would have a real positive value 0.707 times its peak amplitude, and these would all sum together in the same direction. By contrast, if there is a general haphazard distribution of 1's and 0's in the data, the expected peak value in the average symbol would be much lower, although once in a while peaks will still occur.
On observing the output from a sequence of IFFT operations used to encode a (generalised) data sequence for transmission, the signal is seen to have a sample amplitude distribution which is very like random noise, when considered on a statistical basis. The most frequently occurring sample amplitudes are those near zero (the central point—the distribution is symmetrical either side of zero). Higher amplitudes are less likely, but still occur, and there is a gradual reduction in likelihood of occurrence with increasing amplitude. The very highest sample amplitudes which can occur—unlike with true noise there is a finite limit because we use a discrete IFFT over a finite number of tones—are still many times higher than the average signal amplitude; however, such values occur only extremely infrequently.
The overall statistical properties of the sequence are complex. However, one simple measure of the properties of signals generally is their crest factor. The crest factor of a repetitive signal is defined as the ratio of its peak amplitude to its average (RMS) amplitude. Different types of waveforms can have very different crest factors, depending on their shape. For example a simple pulse waveform, where the signal jumps between just two levels +A and −A, has a crest factor of 1, i.e. the average and peak levels of the signal are the same. A simple continuous sine wave has a crest factor of √2 (1.4142135 . . . ). Other wave shapes can be envisaged having widely differing crest factors.
When we are dealing with irregular (non-repeating) signals, such as the output from an IFFT process applied to a random stream of data, the definition of crest factor is adjusted. This is necessary, in order to take into account the statistical spread of amplitude values. In such cases we define the effective crest factor to be the ratio of a threshold level to the average (RMS) level of the signal overall, where the threshold level is that which only some particular small fraction (e.g. 1/10,000,000th, or 10−7) of the generated samples Will equal or exceed.
With signals created by an IFFT-based modulator, in general, systems in which few tones are used will have a smaller effective crest factor than systems with large numbers of tones. In a typical ADSL system, using 220 tones on the downstream path, the effective crest factor is around 5.3 at the 10−7 probability threshold.
In practical systems based on the IFFT/FFT pairing, various steps are taken to reduce the impact of its sensitivity to regular patterns of input data. These can readily occur in data sequences delivered to an encoder, especially in the case of ADSL where a fixed padding data pattern must be inserted when no user data is waiting to be transmitted. The problem of such regular patterns in the original data causing high peaks in the output of the IFFT is usually dealt with by performing a reversible “scrambling” operation on the data stream prior to encoding. Two examples of such scrambling mechanisms are self-scramblers and randomisers.
By applying scrambling processes to the input data, any regular patterns in it may be broken up. The distribution of the data bit values going forward into the encoder becomes more haphazard, and so the likelihood of coherence between the phases of the different tones is drastically reduced. This diminishes the frequency with which spikes appear in the time-domain signal, even for a completely regular input stream (e.g. all 1s), relative to that which would apply without scrambling. However, for more irregular input data, no particular change in the statistical properties of the IFFT output will occur.
One major problem with IFFT-based encoding, so far as the design of any practical system is concerned, is that the time domain signal created has characteristics which make it more difficult and/or more expensive to carry through the later stages of the transmission path. For example, the bandwidth of the signal may in some cases be as wide as can theoretically be carried by the discrete sample sequence. Any subsequent processing of the signal, post-IFFT, must therefore be carefully designed to minimise distortions of the signal caused by frequency-dependent variations (e.g. in gain or phase-shift), which are typically worst at the highest frequencies.
However, an issue of great concern is the high crest factor of a typical IFFT-generated signal. This leads to a number of difficulties in designing the circuitry in a modulator & transmitter for an IFFT-based modulation scheme. Some of the problems also occur in the design of a corresponding multi-tone receiving device.
The first problem is that the dynamic range of the digital-to-analogue converter (DAC) must be large, requiring a relatively high number of bits of resolution (typically between 14 and 16 for ADSL). This makes the DAC hard to design, especially since it is running at high sampling rates (in the order of 1-2 MHz or higher for ADSL, and higher still for COFDM). In a receiver for the transmitted signal, the input circuitry must also have a high dynamic range and low noise and distortion; equally its analogue-to-digital converter must have high linearity and resolution.
The second aspect, which is usually considered even more serious, is that it is extremely difficult to design the amplification stages of the transmitter to both-yield the high linearity which is needed and also maintain good power efficiency. Because the amplifier (also called the “line-driver” in the case of ADSL) must be able to handle signal peaks several times higher than the average signal level on the line, it becomes necessary to run its power supply at a far higher voltage than the average signal level would require, if the signal's crest factor were lower. Typical power efficiencies for amplifiers in present-day ADSL, system designs are therefore significantly lower than in some other types of transmission system e.g. 15-20% as against 40% or more.
Accordingly, it would be beneficial to reduce the crest factor.
An existing patent which describes a technique for reducing the crest factor is U.S. Pat. No. 5,768,318. In that design, the peak value in each symbol produced by the IFFT is first found, by checking each sample which it contains. If the peak lies below the defined threshold, nothing further need be done and the symbol can be transmitted. Otherwise, when the threshold has been exceeded, a special modification is applied to the input vectors of the IFFT (representing the phase and magnitude of each tone), and the IFFT operation is re-run on the modified vectors. The modification is defined in terms of a scaling and phase rotation for each vector. In the general case described in the prior art, this operation may be applied repeatedly, using different modifications of the vectors each time, selecting whichever first results in a peak below the threshold in the resultant time-domain sample sequence created for the symbol.
The prior art patent also describes a possible implementation in which multiple modifications of the vectors and the IFFT operations on each set of modified vectors are executed in parallel, with a selection being performed between the different resulting time-domain waveforms (each held in a buffer) for one which gives a suitable low peak. This scheme reduces the time penalty implied by repeated sequential vector-modification and IFFT operations, but at the cost of greater hardware size, including more buffers.
Now in order for the decoder at the receiving equipment to know what modification of the vectors (if any) was performed, and hence be able to reverse it so as to decode the original information carried, two things are necessary: (a) the modifications are done in accordance with a fixed set of definitions known by both transmitter and receiver; (b) at least one tone must be reserved in the signal spectrum used to carry the symbol. The data modulated onto the reserved tone(s) is an index value ranging over [0 . . . N] identifying whether any modification was performed, and if so which out of N possible modifications was actually used in the symbol as transmitted. The reserved tone(s) clearly must not be modified themselves, and are not available to carry ordinary data.
The main disadvantages of this scheme are:
(a) It requires both transmitter and receiver to co-operate in order to apply the process. The receiver is required to agree with the transmitter about the reserved tones used to carry the modification index. Then, on reception of every symbol, the receiver must first identify the index of the modification applied (by decoding the reserved tones), and if appropriate perform the reverse processing on the output of its FFT operation, before it can continue with the decoding process. This will take extra computation capability, and time, at the receiver.
(b) It consumes data bandwidth for the reserved tone(s) to carry the modification index information; this reduces the bandwidth left for user data.
(c) The carriage of the modification index value must be especially reliable—if the index is decoded incorrectly, the whole symbol cannot be decoded. To provide the additional reliability, either extra bits for forward error correction (such as a CRC), must be sent along with the index value itself, or else the degree of noise margin required when modulating the reserved tone(s) must be set much higher than normal for the main data-carrying tones, or some other method of protection must be applied to that information. Whatever scheme is used will inevitably take more data bandwidth than the same number of bits would need in the main body of user data, so the available user data bandwidth is further reduced.
(d) In the context of standards-conformant ADSL systems, the technique is incompatible with existing standards. Only if the two modems involved both support the technique in the same way can it be used. To do so they must use standards-compatible methods to identify each other's capability in this regard, early in the negotiation phase of initialising the link, before the tones have been allocated to data. Then some proprietary method must be used to set up and activate the extra processing involved at each end of the link. There is no possibility of using this technique when only one of the modems supports it, or if they use differing proprietary methods to implement it. Hence its application is limited.
(e) In many systems using multi-tone modulation, especially by way of example (but not limited to) ADSL modems, it is now very common to use certain pre-processing techniques, including oversampling and signal filtering, in that part of the transmitter circuitry which leads up to the DAC (Digital-to-Analogue-Converter) and thence to the line driver, within what is usually termed the analogue front end (AFE).
Oversampling is a well-known scheme where the sample rate of a (usually digital) sample stream is deliberately increased, typically by an integer factor (say ×2 or ×4), relative to the basic sample rate of the input signal (in our case, the succession of samples forming the symbol as created by the IFFT), for ease of performing certain types of processing on it. The use of oversampling and/or signal filtering presents a problem for the concept of symbol re-generation. Symbol re-generation is applied when peaks in the time-domain representation of a symbol exceed a pre-defined threshold. But the up-sampling process which creates the oversampled stream will itself inevitably cause changes to the symbol shape as viewed in the time domain. This happens because any signal filtering applied, and/or the filter required in any up-sampler (over-sampling block), are bound to cause at least some changes in the relative phase and amplitude of the individual tones of the symbol. Even quite small effects of this sort can have a significant effect on the time-domain shape of the symbol. In particular, the result may be to radically change the location and—most critically—the value of the peak sample in a given symbol (compared to the original shape created by the IFFT), yielding higher peaks in some cases and lower ones in others. The signal filtering operations which may be carried out in relation to multi-tone transmission include band-pass filtering (typically required in COFDM transmission systems) and high-pass filtering (commonly needed for ADSL transmitters).
Such changes are benign, so far as the receiving modem is concerned (much larger effects are normally caused later in the communication path, especially in some types of analogue component, so the receiving modem must compensate for these effects in any case). But, in a modulator which uses oversampling, checking for the peak value in a symbol immediately at the output of the IFFT stage may well give rise to false results. A symbol which does not appear to contain a peak above the threshold at the IFFT output may turn out to have a higher peak after oversampling; alternatively a symbol with a high peak post-IFFT may actually have a reduced peak value as a result of oversampling. Thus, the choice of whether or not to attempt to re-generate the symbol would be erroneous in both cases. In the first case no re-generation would occur, yet the symbol presented to the line driver could have a peak above the threshold, causing the actual transmitted crest factor to be higher than intended, and possibly giving rise to unwanted effects such as distortion of the transmitted signal, because the line driver could be over-driven by the signal. In the second case, the effort spent to re-generate the symbol would have been wasted, since the original symbol, as it would have been seen at the line driver input, would not have contained a significant peak anyway.
Accordingly, there remains a need for an improved method of crest factor reduction and improved apparatus implementing the improved method.